package com.atwy.graph.mst;

import com.atwy.graph.uf.UF_03;

import java.util.*;

/**
 * @Author: 小王子火
 * @Date: 2022/3/16
 * 最小生成树--Kruskal算法
 * 算法思想：按照边的权重顺序（从小到大）处理它们，将边加入最小生成树中，
 * 加入的边不会与已经加入的边构成环，直到树中含有V-1条边为止。
 * 这些边逐渐由一片森林合并成一棵树，也就是图的最小生成树。
 */
public class MST_Kruskal {

    public static void main(String[] args) {
        MST_Kruskal kruskal = new MST_Kruskal();
        int N = 3;
        int[][] connections = {{1,2,5},{1,3,6},{2,3,1}};
        int minimumCost = kruskal.minimumCost(N, connections);
        System.out.println("最小代价是：" + minimumCost);
    }

    /**
     * 力扣 1135
     * 1. 题目
     * 想象一下你是个城市基建规划者，地图上有 N 座城市，它们按以 1 到 N 的次序编号。
     *
     * 给你一些可连接的选项 connections，
     * 其中每个选项 connections[i] = [city1, city2, cost] 表示将城市 city1 和城市 city2 连接所要的成本。
     * （连接是双向的，也就是说城市 city1 和城市 city2 相连也同样意味着城市 city2 和城市 city1 相连）。
     *
     * 返回使得每对城市间都存在将它们连接在一起的连通路径（可能长度为 1 的）最小成本。
     * 该最小成本应该是所用全部连接代价的综合。如果根据已知条件无法完成该项任务，则请你返回 -1。
     *
     * 输入：N = 3,connections = [[1,2,5],[1,3,6],[2,3,1]]
     * 输出：6
     * 解释: 选出任意2条边都可以连接所有城市，我们从中选取成本最小的2条。
     */
    int minimumCost(int n, int[][] connections) {
        // 城市编号为 1...n，所以初始化大小为 n + 1
        UF_03 uf = new UF_03(n+1);
        // 对所有边按照权重从小到大排序
        Arrays.sort(connections, Comparator.comparingInt(a -> a[2]));// 关键1，最小堆
        // 记录最小权重的和
        int mst = 0;
        for (int[] edge : connections){
            int u = edge[0];
            int v = edge[1];
            int weight = edge[2];
            // u,v会产生环，不加入mst
            if(uf.connected(u,v)){ // 关键2，并查集
                continue;
            }
            // 若这条边不会产生环，则属于最小生成树
            mst += weight;
            uf.union(u,v);
        }
        // 保证所有节点都被连通
        // 按理说 uf.count() == 1 说明所有节点被连通
        // 但因为节点 0 没有被使用，所以 0 会额外占用一个连通分量
        return uf.count() == 2 ? mst : -1;
    }

    /**
     * 力扣 1584
     * 问题描述
     * 给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。
     * 连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。
     * 请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。
     *
     * 输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
     * 输出：20
     * 解释：
     * 我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。
     * 注意到任意两个点之间只有唯一一条路径互相到达。
     *
     *
     * @param points
     * @return
     */
    int minCostConnectPoints(int[][] points) {
        int n = points.length;
        // 生成所有边及权重
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int xi = points[i][0], yi = points[i][1];
                int xj = points[j][0], yj = points[j][1];
                // 用坐标点在 points 中的索引表示坐标点
                edges.add(new int[] {
                        i, j, Math.abs(xi - xj) + Math.abs(yi - yj)
                });
            }
        }
        // 将边按照权重从小到大排序
        Collections.sort(edges, Comparator.comparingInt(a -> a[2]));
        // 执行 Kruskal 算法
        int mst = 0;
        UF_03 uf = new UF_03(n);
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int weight = edge[2];
            // 若这条边会产生环，则不能加入 mst
            if (uf.connected(u, v)) {
                continue;
            }
            // 若这条边不会产生环，则属于最小生成树
            mst += weight;
            uf.union(u, v);
        }
        return mst;
    }

}
